☝ PGCD(a;b) ou PGCD(b;a) ? - Remarque

Soit \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) tels que \((a;b) \neq (0;0)\) .

On a :  \(\mathrm{PGCD}(a;b)=\mathrm{PGCD}(b;a)\) . En effet, les ensembles  \(\mathscr{D}(a;b)\)  et  \(\mathscr{D}(b;a)\)  sont égaux, donc ont le même plus grand élément.

Par ailleurs, l'algorithme d'Euclide fonctionne « même si »  \(a.

Exemple

Calculons le PGCD de  \(195\) et \(315\) .

On utilise l'algorithme d'Euclide :
\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 195&315&0&195 \\ \hline 315& 195& 1& 120\\ \hline 195& 120& 1& 75\\ \hline 120& 75& 1& 45\\ \hline 75& 45 & 1& 30\\ \hline 45& 30& 1 & 15\\ \hline 30& 15& 2& 0\\ \hline \end{array}\end{align*}\)

donc \(\mathrm{PGCD}(195;315)=15\) .